package com.example.javamaday.leetcode;

public class LeetCodeTest0053 {

    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{-2, 1}));
    }

    /**
     * 左神解法
     */
     /* public static int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur += nums[i];
            max = Math.max(max, cur);
            cur = Math.max(cur, 0);
        }
        return max;
    }      */


    /**
     * 解法1：leetcode 官方解答
     */
    public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] result = new int[nums.length];
        result[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (result[i - 1] > 0) {
                result[i] = result[i - 1] + nums[i];
            } else {
                result[i] = nums[i];
            }
        }
        int max = nums[0];
        for (int i = 0; i < result.length; i++) {
            if (max < result[i]) {
                max = result[i];
            }
        }
        return max;
    }

}
